package leetcode;

import java.util.Arrays;

public class Q0045 {
    /**
     * O(n^2) O(n)
     **/
    public int jump(int[] nums) {
        int[] f = new int[nums.length];
        Arrays.fill(f, 0x3f3f3f3f);
        f[0] = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            if (i == 0 || f[i] < 100000) {
                for (int j = 1; j <= nums[i]; j++) {
                    if (i + j < nums.length) {
                        f[i + j] = Math.min(f[i + j], f[i] + 1);
                    }
                }
            }
        }
        return f[nums.length - 1];
    }
}
